We give a high precision polynomial-time approximation scheme for thesupremum of any honest n-variate (n+2)-nomial with a constant term, allowingreal exponents as well as real coefficients. Our complexity bounds count fieldoperations and inequality checks, and are polynomial in n and the logarithm ofa certain condition number. For the special case of polynomials (i.e., integerexponents), the log of our condition number is quadratic in the sparseencoding. The best previous complexity bounds were exponential in the sparseencoding, even for n fixed. Along the way, we extend the theory ofA-discriminants to real exponents and certain exponential sums, and find newand natural NP_R-complete problems.
展开▼
